package day_2022_9_to_12.Day;

import java.util.Arrays;

/**
 * @author haomin
 * @date 2022/09/14 11:57
 **/
public class Day12_2_Num322_CoinChange {
    // 动态规划
    public class Solution {
        public int coinChange(int[] coins, int amount) {
            int max = amount + 1;
            int[] dp = new int[amount + 1];
            Arrays.fill(dp, max);
            dp[0] = 0;
            for (int i = 1; i <= amount; i++) {
                for (int j = 0; j < coins.length; j++) {
                    if (coins[j] <= i) {
                        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                    }
                }
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }
    }

    // dfs

//    static int minCount = Integer.MAX_VALUE;
//    public static int coinChange(int[] coins, int amount) {
//        if(amount == 0) return 0;
//        if(coins.length == 0) return -1;
//        Arrays.sort(coins);
//        dfs(coins, coins.length-1, amount, 0);
//        return minCount == Integer.MAX_VALUE ? -1 : minCount;
//    }
//    private static void dfs(int[] coins, int n, int amount, int count){
//        System.out.println(amount);
//        if(amount == 0){
//            minCount = Math.min(minCount, count);
//            return;
//        }
//        if(amount < 0) return;
//        for(int i = n; i >= 0; --i){
//            amount -= coins[i];
//            dfs(coins, n, amount, count+1);
//            amount += coins[i];
//        }
//    }



//    public static int coinChange(int[] coins, int amount) {
//        if(coins.length == 0 || amount == 0) return -1;
//        Arrays.sort(coins);
//        int r = coins.length-1;
//        int count = 0;
//        while(r >= 0 && amount > 0){
//            while(coins[r] <= amount){
//                amount-=coins[r];
//                count++;
//            }
//            r--;
//        }
//        System.out.println(count);
//        System.out.println(amount);
//        return amount == 0 ? count : -1;
//    }
}